package algorithm.sort;

public class QuickSort implements SortAlgorithm {
    @Override
    public void sort(int[] inputArray) {
        quickSort(inputArray, 0, inputArray.length - 1);
    }

    private void quickSort(int[] array, int p, int r) {
        if (p >= r) {
            return;
        }

        int q = getPartition(array, p, r);
        quickSort(array, p, q - 1);
        quickSort(array, q + 1, r);
    }

    private int getPartition(int[] array, int p, int r) {
        int pivot = array[r];
        int i = p;
        for (int j = p; j < r ; j++) {
            if (array[j] < pivot) {
                swap(array, i, j);
                i++;
            }
        }
        swap(array, i, r);
        return i;
    }

    private void swap(int[] array, int p, int q) {
        if (p == q) {
            return;
        }
        int wrap = array[p];
        array[p] = array[q];
        array[q] = wrap;
    }
}
